package com.fr.lintcode;

import org.junit.Test;

/**
*作者：furong
*日期：2017年1月6日
*时间：上午10:56:14
*/
public class Q163 {
    /**
     * @paramn n: An integer
     * @return: An integer
     */
    public int numTrees(int n) {
        if (n <= 1) {
            return 1;
        }
        int[] total = new int[n + 1];
        total[0] = 1;
        total[1] = 1;
        for (int i = 2; i <= n; i++) {
            total[i] = calculate(total, i);
        }
        return total[n];
    }

    private int calculate(int[] total, int i) {
        int count = 0;
        for (int j = 1; j <= i; j++) {
            count += total[j - 1] * total[i - j];
        }
        return count;
    }

    @Test
    public void testA() {
        System.out.println(numTrees(7));
    }

}
